/*-------------------------------------------------
#
# Project created by chenswe
#
#				2015 - 12 - 2
#
#-------------------------------------------------*/


#include"BinaryTree.h"
#include<queue>
#include<stack>

int BinaryTree::outputTip() {

	cout << "\n\nPlease choose the way of output" << endl;
	cout << "1.preOrder\n2.inOrder\n3.postOrder\n4.LevelOrder\n";
	char ch;
	do {
		cin >> ch;
	} while (ch < '1' || ch > '4');
	return ch - '0';
}
//---------------input a tree
istream &operator>>(istream & input, BinaryTree &tree) {
	tree.CreateBiTree();
	return input;
}

//---------------in a non-recursive manner.
ostream &operator<<(ostream & output, BinaryTree & tree) {
	if (tree.isEmpty())
		output << "the tree is empty" << endl;
	else
		switch (tree.outputTip()) {
		case 1:		tree.NonRecurPerVisit();		break;
		case 2:		tree.NonRecurInVisit();			break;
		case 3:		tree.NonRecurPostVisit();		break;
		default:									break;
		}
	return output;
}

//--------------in a recursive manner
//ostream &operator<<(ostream & output, BinaryTree & tree) {
//	if (tree.isEmpty())
//		output << "the tree is empty" << endl;
//	else
//		switch (tree.outputTip()) {
//		case 1:		tree.Traverse(PRE);			break;
//		case 2:		tree.Traverse(IN);			break;
//		case 3:		tree.Traverse(POST);		break;
//		case 4:		tree.Traverse(LEVEL);		break;
//		default:								break;
//		}
//	return output;
//}

BinaryTree::BinaryTree(char data,
	BinaryTree *lchild,
	BinaryTree *rchild)
	:m_cData('#'), m_LChild(NULL),
	m_RChild(NULL) {
}
 
BinaryTree ::BinaryTree(BinaryTree &tree){
	BinaryTree *ptr = this;
	*ptr = tree;
}

//-------copy a tree
//-----------For each node in the tree,copy left subtree first, 
//-----------at the same time, store right subtree in a Stack
void BinaryTree::operator=(BinaryTree &tree){
	if (!this->isEmpty()) {
		this->clear();
	}
	stack<BinaryTree*> Stack1, Stack2;
	BinaryTree *ptr1 = this;			//point to the node in the new tree
	BinaryTree *ptr2 = &tree;			//point to the node in the old tree
	Stack1.push(ptr1);					//store right subtrees' pointer of new tree
	Stack2.push(ptr2);					//store right subtrees' pointer of old tree
	
	while (!Stack2.empty()) {			
		ptr1 = Stack1.top();
		Stack1.pop();
		ptr2 = Stack2.top();
		Stack2.pop();
		do {
			if (ptr2->getRChild() != NULL) {		
				ptr1->setRChild(new BinaryTree);
				if (ptr1->getRChild() == NULL) {
					cout << "Failed to copy tree!" << endl;
					return;
				}
				else
					Stack1.push(ptr1->getRChild());
				Stack2.push(ptr2->getRChild());
			}
			ptr1->setData(ptr2->getData());
			if (ptr2->getLChild() != NULL) {
				ptr1->setLChild(new BinaryTree);
				if (ptr1->getLChild() == NULL) {
					cout << "Failed to copy tree!" << endl;
					return;
				}
				else
					ptr1 = ptr1->getLChild();
			}
			ptr2 = ptr2->getLChild();
		} while (ptr2 != NULL);
	}
}


//--------------Tracerse in a recursive manner
Status BinaryTree::Traverse(ways way) {
	if (way == PRE) {
		return	recurPreOrderTraverse();
	}
	else if (way == IN) {
		return recurInOrderTraverse();
	}
	else if (way == POST) {
		return recurPostOrderTraverse();
	}
	else if (way == LEVEL) {
		return levelOrderTraverse();
	}
	return ERROR;
}

Status BinaryTree::CreateBiTree(){
	char data;
	cin >> data;
	if (data != '#') {
		if (!(this->setLChild(new BinaryTree) &&
			this->setRChild(new BinaryTree)))
			exit(EXIT_FAILURE);

		this->setData(data);
		
		this->getLChild()->CreateBiTree();
		if (this->getLChild()->getData() == '#') {
			delete this->getLChild();
			this->setLChild(NULL);
		}
		
		this->getRChild()->CreateBiTree();
		if (this->getRChild()->getData() == '#') {
			delete this->getRChild();
			this->setRChild(NULL);
		}
	}
	return OK;
}

BinaryTree::~BinaryTree() {
	if (this->getData() != '#')
		this->clear();
}

Status BinaryTree::visit() {
	cout << this->getData() << " ";
	return OK;
}

char BinaryTree::getData() const {
	return m_cData;
}

BinaryTree *BinaryTree::getLChild() const {
	return m_LChild;
}

BinaryTree *BinaryTree::getRChild() const {
	return m_RChild;
}

Status BinaryTree::setData(char data) {
	m_cData = data;
	return OK;
}

Status BinaryTree::setLChild(BinaryTree *child) {
	m_LChild = child;
	return OK;
}

Status BinaryTree::setRChild(BinaryTree *child) {
	m_RChild = child;
	return OK;
}
 
//---------clear a tree
Status BinaryTree ::clear(){
	stack<BinaryTree*> Stack1, Stack2;
	Stack1.push(this);
	BinaryTree *ptr;
	while (!Stack1.empty()) {
		ptr = Stack1.top();
		Stack1.pop();

		ptr->setData('#');
		Stack2.push(ptr);
		do {
			if (ptr->getLChild() != NULL)
				Stack1.push(ptr->getLChild());
			if (ptr->getRChild() != NULL) {
				ptr->getRChild()->setData('#');
				Stack2.push(ptr->getRChild());
			}
			ptr = ptr->getRChild();
		} while (ptr != NULL);
	}
	while (!Stack2.empty()) {
		ptr = Stack2.top();
		Stack2.pop();
		if (ptr == this) {
			ptr->setData('#');
			ptr->setLChild(NULL);
			ptr->setRChild(NULL);
		}
		else
			delete ptr;
	}
	return OK;
}

bool BinaryTree::isEmpty() {
	return	this->getData() == '#';
}
 
int BinaryTree ::getDepth(){
	if (this == NULL)
		return 0;
	int depth1 = this->getLChild()->getDepth();
	int depth2 = this->getRChild()->getDepth();
	return (depth1 > depth2 ? depth1 : depth2) + 1;
}

int BinaryTree::getNodeNum(){
	int count = 0;
	stack<BinaryTree*> Stack;
	Stack.push(this);
	BinaryTree *ptr;
	while (!Stack.empty()) {
		ptr = Stack.top();
		Stack.pop();
		do {
			if (ptr->getData() != '#')
				++count;
			if (ptr->getRChild() != NULL)
				Stack.push(ptr->getRChild());
			ptr = ptr->getLChild();
		} while (ptr != NULL);
	}
	return count;
}
 
int BinaryTree ::getLeafNum(){
	if (this == NULL)	return 0;
	if (this->getLChild() == NULL && this->getRChild() == NULL)
		return 1;
	int left = this->getLChild()->getLeafNum();
	int right = this->getRChild()->getLeafNum();
	return left + right;
}

Status BinaryTree::swap(){
	if (this != NULL) {
		if (this->getLChild() == NULL &&
			this->getRChild() == NULL)
			return OK;

		BinaryTree *temp = this->getLChild();
		this->setLChild(this->getRChild());
		this->setRChild(temp);

		this->getLChild()->swap();
		this->getRChild()->swap();
		return OK;
	}
	return OK;
}

Status BinaryTree::preOrderfind(int &index, const int total){
	
	if (this != NULL) {
		if (index < 1 || index > total) {
			cout << "Not exist!" << endl;
			return ERROR;
		}
		if (index == 1) {
			cout << this->getData() << endl;
			return OK;
		}

		return this->getLChild()->preOrderfind(--index,total) ||
			this->getRChild()->preOrderfind(--index,total);
	}
	else {
		++index;
		return ERROR;
	}
}

bool BinaryTree ::operator==(BinaryTree &tree){
	BinaryTree *ptr = &tree;
	if (this == NULL && ptr == NULL)
		return true;
	else if (this == NULL || ptr == NULL)
		return false;
	else {
		if (this->getData() == ptr->getData()) {
			if (*this->getLChild() == *ptr->getLChild()) {
				if (*this->getRChild() == *ptr->getRChild())
					return true;
			}
		}
		return false;
	}
}

bool BinaryTree::similar(BinaryTree &tree){
	BinaryTree *ptr = &tree;
	if (this == NULL && ptr == NULL)
		return true;
	else if (this == NULL || ptr == NULL)
		return false;
	else {
		if (this->getLChild()->similar(*ptr->getLChild())) 
			if (this->getRChild()->similar(*ptr->getRChild()))
				return true;
		return false;
	}
}

Status BinaryTree::recurPreOrderTraverse() {
	if (this != NULL) {
		if (this->visit())
			if (this->getLChild()->recurPreOrderTraverse())
				if (this->getRChild()->recurPreOrderTraverse())
					return OK;
		return ERROR;
	}
	return OK;
}

Status BinaryTree::recurInOrderTraverse() {
	if (this != NULL) {
		if (this->getLChild()->recurInOrderTraverse())
			if (this->visit())
				if (this->getRChild()->recurInOrderTraverse())
					return OK;
		return ERROR;
	}
	return OK;
}

Status BinaryTree::recurPostOrderTraverse() {
	if (this != NULL) {
		if (this->getLChild()->recurPostOrderTraverse())
			if (this->getRChild()->recurPostOrderTraverse())
				if (this->visit())
					return OK;
		return ERROR;
	}
	return OK;
}

Status BinaryTree::levelOrderTraverse(){
	queue<BinaryTree*> Queue;
	Queue.push(this);
	BinaryTree *ptr;
	while (!Queue.empty()){
		ptr = Queue.front();
		Queue.pop();
		ptr->visit();
		if (ptr->getLChild())	Queue.push(ptr->getLChild());
		if (ptr->getRChild())	Queue.push(ptr->getRChild());
	}
	return OK;
}

Status BinaryTree::NonRecurPerVisit(){
	stack<BinaryTree*> Stack;
	Stack.push(this);
	BinaryTree *ptr;
	while (!Stack.empty()) {
		ptr = Stack.top();
		Stack.pop();
		do {
			if (!ptr->visit())
				return ERROR;
			if (ptr->getRChild() != NULL)
				Stack.push(ptr->getRChild());
			ptr = ptr->getLChild();
		} while (ptr != NULL);
	}
	return OK;
}

Status BinaryTree::NonRecurInVisit(){
	stack<BinaryTree*> Stack;
	Stack.push(this);
	BinaryTree *ptr;
	bool flag = true;			//a new element added
	while(!Stack.empty()){
		ptr = Stack.top();
		Stack.pop();
		if(flag == true)
			while (ptr->getLChild() != NULL) {
				Stack.push(ptr->getLChild());
				ptr = ptr->getLChild();
			}

		if (!ptr->visit())		//failed to visit
			return ERROR;

		if (ptr->getRChild() != NULL) {		//a new element added
			Stack.push(ptr->getRChild());
			flag = true;
		}
		else
			flag = false;
	}
	return OK;
}

Status BinaryTree::NonRecurPostVisit(){
	stack<BinaryTree*> Stack1,Stack2;
	Stack1.push(this);
	BinaryTree *ptr;
	while (!Stack1.empty()) {
		ptr = Stack1.top();
		Stack1.pop();
		Stack2.push(ptr);
		do {
			if (ptr->getLChild() != NULL)
				Stack1.push(ptr->getLChild());
			if (ptr->getRChild() != NULL) 
				Stack2.push(ptr->getRChild());
			ptr = ptr->getRChild();
		} while (ptr != NULL);
	}
	while (!Stack2.empty()) {
		ptr = Stack2.top();
		Stack2.pop();
		if (!ptr->visit())
			return ERROR;
	}
	return OK;
}
